package shapes.shapes2D.distribution.poissondisk 
{
	import flash.display.Graphics;
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import shapes.shapes2D.Dot;
	import utils.GeomUtils;
	
	/**
	 * 
	 * http://www.devmag.org.za/articles/55-POISSON-DISK-SAMPLING/#top2
	 * 
	 * @author Nicolas Barradeau
	 * http://en.nicoptere.net
	 */
	public class PoissonDisk
	{
		static private var cellSize:Number;
		
		static private var min_dist_square:Number;
		
		static private var grid:Vector.<Vector.<Point>>;
		static private var processList:Vector.<Point>;
		static private var samplePoints:Vector.<Point>;
		static private var width:int;
		static private var height:int;
		
		
		static private var totalCell:int;
		static private var num_col:int;
		static private var num_row:int;
		static private var maxAttempts:int = 50;
		
		public function PoissonDisk() 
		{
			
		}
		static public function generate_poisson( rect:Rectangle, min_dist:Number = 10, new_points_count:int = 50 ):Vector.<Point>
		{
			//Create the grid
			cellSize = min_dist / Math.SQRT2;
			
			
			min_dist_square = min_dist * min_dist;
			
			width = rect.width;
			height = rect.height;
			
			num_col = int( width / cellSize ) + 1;
			num_row = int( height / cellSize ) + 1;
			
			totalCell = num_col * num_row;
			
			//if ( new_points_count > totalCell ) new_points_count = totalCell;
			trace( totalCell, new_points_count, num_col, num_row );
			
			grid = new Vector.<Vector.<Point>>();
			
			var i:int;
			for ( i = 0; i < num_col; i++ )
			{
				grid.push( new Vector.<Point>() );
				grid[ i ].length = num_row;
			}
			
			//generate the first point randomly
			//and updates 

			//var point:Point = new Point( Math.random() * width, Math.random() * height );
			var point:Point = new Point( width * .5, height * .5 );
			var newPoint:Point;
			
			//RandomQueue works like a queue, except that it
			//pops a random element from the queue instead of
			//the element at the head of the queue
			processList = Vector.<Point>( [ point ] );
			samplePoints = Vector.<Point>( [ point ]  );

			setPointToGrid( point );
			var found:Boolean;
			
			//return samplePoints
			//generate other points from points in queue.
			while ( samplePoints.length <= new_points_count )
			{
				
				var r:int = int( Math.random() * processList.length );
				point = processList[ r ];
				
				found = false;
				search:for (i = 0; i < 1000; i++)
				{
					
					newPoint = generateRandomPointAround( point, min_dist );
					
					//check that the point is in the image region
					//and no points exists in the point's neighbourhood
					
					if ( 	rect.contains( newPoint.x, newPoint.y )
					&&		!inNeighbourhood( newPoint, min_dist ) )
					{
						
						//update containers
						found = true;
						break search;
					}
					
				}
				
				if ( found )
				{
					processList.splice( r, 1 );
					processList.push(newPoint);
					samplePoints.push(newPoint);
					setPointToGrid( newPoint );
				}
				
			}
			trace( samplePoints.length );
			return samplePoints;
		}
		
		static private function getRandomGridPoint():Point
		{
			return grid[ int( Math.random() * num_col ) ][ int( Math.random() * num_row ) ];
		}
		
		static private function generateRandomPointAround( point:Point, mindist:Number ):Point
		{
			
			//random radius between mindist and 2 * mindist
			var radius:Number = mindist + ( mindist * Math.random() );
			
			//random angle
			var angle:Number = ( 2 * Math.PI ) * Math.random();
			
			//the new point is generated around the point (x, y)
			return new Point( 	point.x + radius * Math.cos(angle),
								point.y + radius * Math.sin(angle) 	);
		
		}
		
		static private function inNeighbourhood( point:Point, mindist:Number ):Boolean
		{
			//if ( grid.length <= 0 ) return false;
			//var p:Point 
			//var dx:Number, dy:Number;
			//for each( var p:Point in grid )
			//{
				//
				//if ( null != p )
				//{
					//dx = point.x - p.x;
					//dy = point.y - p.y;
					//if ( ( dx * dx + dy * dy ) < min_dist_square ) return true;
				//}
				//
			//}
			//
			
			var p:Point;
			var dx:Number, dy:Number;
			var i:int, j:int;
			
			var x:int = int( point.x / cellSize )-1;
			var y:int = int( point.y / cellSize )-1;
			
			
			var min:int = 2;
			var max:int = 2;
			
			var minx:int = ( x - min <= 0 ) ? 0 : ( x - min );
			var maxx:int = ( x + max >= num_col ) ?  ( num_col ) : ( x + max );
			
			var miny:int = ( y - min <= 0 ) ? 0 : ( y - min );
			var maxy:int = ( y + max >= num_row ) ?  ( num_row ) : ( y + max );
			
			//trace( x, y, minx, maxx, miny, maxy );
			
			for ( i = minx; i < maxx; i++ )
			{
				for ( j = miny; j < maxy; j++ )
				{
					if ( grid[ i ] [ j ] != null )
					{
						p = grid[ i ] [ j ];
						dx = point.x - p.x;
						dy = point.y - p.y;
						if ( ( dx * dx + dy * dy ) < min_dist_square ) return true;
					}
				}
			}
			return false
			
			//get the neighbourhood if the point in the grid
			//cellsAroundPoint = squareAroundPoint( imageToGrid( point ) );
			//
			//var p:Point = grid[ imageToGrid( point ) ];
			//var center:int =  imageToGrid( point );
			//var i0:int, i1:int;
			//
			//i0 = center - ( 2 * num_col ) - 1;
			//i1 = center + ( 2 * num_col ) + 1;
			//
			//if ( i0 < 0 ) i0 = 0;
			//if ( i1 >= totalCell ) i1 = totalCell - 1;
			//
			//var tl:Point = 
			//
			//
			//for every cell in cellsAroundPoint
				//if (cell != null)
				//if distance(cell, point) < mindist
				//return true
		}
		
		static private function squareAroundPoint( id:int ):Vector.<Point>
		{
			var cells:Vector.<Point> = new Vector.<Point>();
			return cells;
		}
		
		static private function setPointToGrid( point:Point ):void
		{
			//trace(point, num_col, num_row, int( point.x / cellSize ) , int( point.y / cellSize ) );
			
			grid[ int( point.x / cellSize ) ][ int( point.y / cellSize )  ] = point;
			//try {}catch ( e:Error ) { };
		}
		
		static private function imageToGrid( point:Point ):Point
		{
			return grid[ int( point.x / cellSize ) ][ int( point.y / cellSize )  ];
		}
		
		
	}

}
	